#include <string>
#include <sstream>
#include <stack>
#include "tree_node.h"

//serialize by preorder with nullptr
std::string preorder_serialize(const std::shared_ptr<Node>& root) {
	char null_marker = '#';
	std::stringstream sstr;
	std::stack<std::shared_ptr<Node> > stack;
	stack.push(root);
	while (!stack.empty() ) {
		std::shared_ptr<Node> curr = stack.top();
		stack.pop();
		if ( curr != nullptr) {
			sstr << curr->key << ' ';
			stack.push(curr->right);
			stack.push(curr->left);
		}
		else
			sstr << null_marker << ' ';
	}
	return sstr.str();
}

//return the root node
std::shared_ptr<Node> preorder_deserialize(std::string str) {
	std::stringstream sstr(str);
	std::stack<std::shared_ptr<Node>> stack;
	std::shared_ptr<Node> root(new Node);
	std::shared_ptr<Node> curr = root;
	sstr >> curr->key;
	std::shared_ptr<Node> next;
	while (sstr) {
		char c;
		sstr.get(c);
		if (sstr.gcount() == 0)
			break;
		while ( c == ' ' ) {
			sstr.get(c);
			if (sstr.gcount() == 0)
				break;
		}
		if (sstr.gcount() == 0)
			break;
		if (c == '#')
			next = nullptr;
		else {
			sstr.unget();
			next = std::shared_ptr<Node>(new Node);
			sstr >> next->key;
		}
		if (curr != nullptr) {
			stack.push(curr);
			curr->left = next;
			if(next)
				next->parent = curr;
			curr = next;
		}
		else {
			curr = stack.top();
			stack.pop();
			curr->right = next;
			if(next)
				next->parent = curr;
			curr = next;
		}
	}
	return root;
}

void test_serialization(){
	std::string str = "1 2 4 # # # 3 # #";
	std::shared_ptr<Node> root = preorder_deserialize(str);
	std::cout << str << std::endl;
	std::cout << preorder_serialize(root) << std::endl;
	std::cout << bfs(root) << std::endl;
	std::cout << level_order_2queue(root) << std::endl;
	std::cout << level_order_1queue(root) << std::endl;
	std::cout << "height of the tree: " << height(root) << std::endl;
	std::cout << "height of the tree: " << bfs_height(root) << std::endl;
}